home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / src / gen / DLList.ccP < prev    next >
Text File  |  1993-11-18  |  6KB  |  340 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. // WARNING: This file is obsolete.  Use ../DLList.cc, if you can.
  3. /* 
  4. Copyright (C) 1988 Free Software Foundation
  5.     written by Doug Lea (dl@rocky.oswego.edu)
  6.  
  7. This file is part of the GNU C++ Library.  This library is free
  8. software; you can redistribute it and/or modify it under the terms of
  9. the GNU Library General Public License as published by the Free
  10. Software Foundation; either version 2 of the License, or (at your
  11. option) any later version.  This library is distributed in the hope
  12. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  13. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  14. PURPOSE.  See the GNU Library General Public License for more details.
  15. You should have received a copy of the GNU Library General Public
  16. License along with this library; if not, write to the Free Software
  17. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  18. */
  19.  
  20. #ifdef __GNUG__
  21. #pragma implementation
  22. #endif
  23. #include <limits.h>
  24. #include <stream.h>
  25. #include <builtin.h>
  26. #include "<T>.DLList.h"
  27.  
  28. // error handling
  29.  
  30.  
  31.  
  32. void <T>DLList::error(const char* msg)
  33. {
  34.   (*lib_error_handler)("DLList", msg);
  35. }
  36.  
  37. int <T>DLList::length()
  38. {
  39.   int l = 0;
  40.   <T>DLListNode* t = h;
  41.   if (t != 0) do { ++l; t = t->fd; } while (t != h);
  42.   return l;
  43. }
  44.  
  45. <T>DLList::<T>DLList(const <T>DLList& a)
  46. {
  47.   if (a.h == 0)
  48.     h = 0;
  49.   else
  50.   {
  51.     <T>DLListNode* p = a.h;
  52.     <T>DLListNode* t = new <T>DLListNode(p->hd);
  53.     h = t;
  54.     p = p->fd;
  55.     while (p != a.h)
  56.     {
  57.       <T>DLListNode* n = new <T>DLListNode(p->hd);
  58.       t->fd = n;
  59.       n->bk = t;
  60.       t = n;
  61.         p = p->fd;
  62.     }
  63.     t->fd = h;
  64.     h->bk = t;
  65.     return;
  66.   }
  67. }
  68.  
  69. <T>DLList& <T>DLList::operator = (const <T>DLList& a)
  70. {
  71.   if (h != a.h)
  72.   {
  73.     clear();
  74.     if (a.h != 0)
  75.     {
  76.       <T>DLListNode* p = a.h;
  77.       <T>DLListNode* t = new <T>DLListNode(p->hd);
  78.       h = t;
  79.       p = p->fd;
  80.       while (p != a.h)
  81.       {
  82.         <T>DLListNode* n = new <T>DLListNode(p->hd);
  83.         t->fd = n;
  84.         n->bk = t;
  85.         t = n;
  86.         p = p->fd;
  87.       }
  88.       t->fd = h;
  89.       h->bk = t;
  90.     }
  91.   }
  92.   return *this;
  93. }
  94.  
  95. void <T>DLList::clear()
  96. {
  97.   if (h == 0)
  98.     return;
  99.  
  100.   <T>DLListNode* p = h->fd;
  101.   h->fd = 0;
  102.   h = 0;
  103.  
  104.   while (p != 0)
  105.   {
  106.     <T>DLListNode* nxt = p->fd;
  107.     delete(p);
  108.     p = nxt;
  109.   }
  110. }
  111.  
  112.  
  113. Pix <T>DLList::prepend(<T&> item)
  114. {
  115.   <T>DLListNode* t = new <T>DLListNode(item);
  116.   if (h == 0)
  117.     t->fd = t->bk = h = t;
  118.   else
  119.   {
  120.     t->fd = h;
  121.     t->bk = h->bk;
  122.     h->bk->fd = t;
  123.     h->bk = t;
  124.     h = t;
  125.   }
  126.   return Pix(t);
  127. }
  128.  
  129. Pix <T>DLList::append(<T&> item)
  130. {
  131.   <T>DLListNode* t = new <T>DLListNode(item);
  132.   if (h == 0)
  133.     t->fd = t->bk = h = t;
  134.   else
  135.   {
  136.     t->bk = h->bk;
  137.     t->bk->fd = t;
  138.     t->fd = h;
  139.     h->bk = t;
  140.   }
  141.   return Pix(t);
  142. }
  143.  
  144. Pix <T>DLList::ins_after(Pix p, <T&> item)
  145. {
  146.   if (p == 0) return prepend(item);
  147.   <T>DLListNode* u = (<T>DLListNode*) p;
  148.   <T>DLListNode* t = new <T>DLListNode(item, u, u->fd);
  149.   u->fd->bk = t;
  150.   u->fd = t;
  151.   return Pix(t);
  152. }
  153.  
  154. Pix <T>DLList::ins_before(Pix p, <T&> item)
  155. {
  156.   if (p == 0) error("null Pix");
  157.   <T>DLListNode* u = (<T>DLListNode*) p;
  158.   <T>DLListNode* t = new <T>DLListNode(item, u->bk, u);
  159.   u->bk->fd = t;
  160.   u->bk = t;
  161.   if (u == h) h = t;
  162.   return Pix(t);
  163. }
  164.  
  165. void <T>DLList::join(<T>DLList& b)
  166. {
  167.   <T>DLListNode* t = b.h;
  168.   b.h = 0;
  169.   if (h == 0)
  170.     h = t;
  171.   else if (t != 0)
  172.   {
  173.     <T>DLListNode* l = t->bk;
  174.     h->bk->fd = t;
  175.     t->bk = h->bk;
  176.     h->bk = l;
  177.     l->fd = h;
  178.   }
  179. }
  180.  
  181. int <T>DLList::owns(Pix p)
  182. {
  183.   <T>DLListNode* t = h;
  184.   if (t != 0 && p != 0)
  185.   {
  186.     do
  187.     {
  188.       if (Pix(t) == p) return 1;
  189.       t = t->fd;
  190.     } while (t != h);
  191.   }
  192.   return 0;
  193. }
  194.  
  195. void <T>DLList::del(Pix& p, int dir)
  196. {
  197.   if (p == 0) error("null Pix");
  198.   <T>DLListNode* t = (<T>DLListNode*) p;
  199.   if (t->fd == t)
  200.   {
  201.     h = 0;
  202.     p = 0;
  203.   }
  204.   else
  205.   {
  206.     if (dir < 0)
  207.     {
  208.       if (t == h)
  209.         p = 0;
  210.       else
  211.         p = Pix(t->bk);
  212.     }
  213.     else
  214.     {
  215.       if (t == h->bk)
  216.         p = 0;
  217.       else
  218.         p = Pix(t->fd);
  219.     }
  220.     t->bk->fd = t->fd;
  221.     t->fd->bk = t->bk;
  222.     if (t == h) h = t->fd;
  223.   }
  224.   delete t;
  225. }
  226.  
  227. void <T>DLList::del_after(Pix& p)
  228. {
  229.   if (p == 0)
  230.   {
  231.     del_front();
  232.     return;
  233.   }
  234.  
  235.   <T>DLListNode* b = (<T>DLListNode*) p;
  236.   <T>DLListNode* t = b->fd;
  237.  
  238.   if (b == t)
  239.   {
  240.     h = 0;
  241.     p = 0;
  242.   }
  243.   else
  244.   {
  245.     t->bk->fd = t->fd;
  246.     t->fd->bk = t->bk;
  247.     if (t == h) h = t->fd;
  248.   }
  249.   delete t;
  250. }
  251.  
  252. <T> <T>DLList::remove_front()
  253. {
  254.   if (h == 0)
  255.     error("remove_front of empty list");
  256.   <T>DLListNode* t = h;
  257.   <T> res = t->hd;
  258.   if (h->fd == h)
  259.     h = 0;
  260.   else
  261.   {
  262.     h->fd->bk = h->bk;
  263.     h->bk->fd = h->fd;
  264.     h = h->fd;
  265.   }
  266.   delete t;
  267.   return res;
  268. }
  269.  
  270.  
  271. void <T>DLList::del_front()
  272. {
  273.   if (h == 0)
  274.     error("del_front of empty list");
  275.   <T>DLListNode* t = h;
  276.   if (h->fd == h)
  277.     h = 0;
  278.   else
  279.   {
  280.     h->fd->bk = h->bk;
  281.     h->bk->fd = h->fd;
  282.     h = h->fd;
  283.   }
  284.   delete t;
  285. }
  286.  
  287. <T> <T>DLList::remove_rear()
  288. {
  289.   if (h == 0)
  290.     error("remove_rear of empty list");
  291.   <T>DLListNode* t = h->bk;
  292.   <T> res = t->hd;
  293.   if (h->fd == h)
  294.     h = 0;
  295.   else
  296.   {
  297.     t->fd->bk = t->bk;
  298.     t->bk->fd = t->fd;
  299.   }
  300.   delete t;
  301.   return res;
  302. }
  303.  
  304.  
  305. void <T>DLList::del_rear()
  306. {
  307.   if (h == 0)
  308.     error("del_rear of empty list");
  309.   <T>DLListNode* t = h->bk;
  310.   if (h->fd == h)
  311.     h = 0;
  312.   else
  313.   {
  314.     t->fd->bk = t->bk;
  315.     t->bk->fd = t->fd;
  316.   }
  317.   delete t;
  318. }
  319.  
  320.  
  321. int <T>DLList::OK()
  322. {
  323.   int v = 1;
  324.   if (h != 0)
  325.   {
  326.     <T>DLListNode* t = h;
  327.     long count = LONG_MAX;      // Lots of chances to find h!
  328.     do
  329.     {
  330.       count--;
  331.       v &= t->bk->fd == t;
  332.       v &= t->fd->bk == t;
  333.       t = t->fd;
  334.     } while (v && count > 0 && t != h);
  335.     v &= count > 0;
  336.   }
  337.   if (!v) error("invariant failure");
  338.   return v;
  339. }
  340.